Growth Rates

Tags: #◇CCDSALG #◇Algorithms #◇Computer Science #◇Computational Complexity #◇Efficiency #◇Algorithm Design Paradigms #◇Analysis of Algorithms #◇Data Structures #◇Time Complexity #◇Space Complexity

◇Overview

Growth rates describe how an algorithm’s resource usage (time or space) increases as the input size $n$ grows.

◇Key Concepts

Growth rate hierarchy from constant to factorial Asymptotic dominance between functions Why lower growth rates are preferred for scalability Connection to ◇Asymptotic Notation and ◇Order of Growth

◇Details / Theory

Definition

The growth rate of a function $f(n)$ describes how quickly $f(n)$ increases as $n \to \infty$ . In algorithm analysis, we care about the growth rate of the ◇Running Time function $T(n)$ because it determines how the algorithm scales.

Hierarchy of Common Growth Rates

From slowest (best) to fastest (worst) growth:

Growth Rate	Name	Example Algorithm
$\Theta(1)$	Constant	Accessing array element by index
$\Theta(\log n)$	Logarithmic	Binary Search
$\Theta(\sqrt{n})$	Square Root	Trial division primality test
$\Theta(n)$	Linear	Linear Search, finding max
$\Theta(n \log n)$	Linearithmic	Merge Sort, Heap Sort
$\Theta(n^2)$	Quadratic	Bubble Sort, checking all pairs
$\Theta(n^3)$	Cubic	Naive matrix multiplication
$\Theta(2^n)$	Exponential	Finding all subsets
$\Theta(n!)$	Factorial	Generating all permutations

Practical Impact

For $n = 1{,}000{,}000$ inputs:

Growth Rate	Approximate Operations
$O(\log n)$	~20
$O(n)$	1,000,000
$O(n \log n)$	~20,000,000
$O(n^2)$	1,000,000,000,000 (infeasible)

Asymptotic Dominance

A function $f(n)$ dominates $g(n)$ if $\lim_{n \to \infty} \frac{g(n)}{f(n)} = 0$ .

The dominance ordering is:
$1 \prec \log n \prec \sqrt{n} \prec n \prec n\log n \prec n^2 \prec n^3 \prec 2^n \prec n!$

Why Growth Rates Matter

An $O(n \log n)$ algorithm will always eventually beat an $O(n^2)$ algorithm for sufficiently large $n$ , regardless of constant factors. Growth rates are what ◇Asymptotic Notation captures by ignoring constants and lower-order terms.

◇Common Pitfalls

Assuming a "faster" growth rate algorithm is always faster — for small $n$ , constants matter. Confusing $O(n \log n)$ with $O(n)$ — the $\log n$ factor makes a real difference for large inputs. Forgetting that exponential and factorial growth rates are generally computationally infeasible.

◇Summary

TL;DR — Growth rates rank how fast an algorithm’s time/space grows with input size. The hierarchy from best to worst is: $O(1) < O(\log n) < O(n) < O(n \log n) < O(n^2) < O(2^n) < O(n!)$ .

◇Links

Related: ◇Order of Growth — ◇Asymptotic Notation — ◇Big-O Notation — ◇Time Complexity — ◇Running Time Source / Reference: Handout 03, Page 17

Previous Topic: ◇Function Calls
Next Topic: ◇Input Size
Related Notes: ◇Algorithm Analysis, ◇Core Concepts

GROWTH RATES